package HelloArithmetic.Hash;



import java.util.ArrayList;

import java.util.List;

/**
 * @program: JavaDataStructure
 * @ClassName _03HashMapChain
 * @description: 解决hash冲突，使用链式存储，即当负载因子超过0.75，则进行扩容，同时存储结构使用链式。
 * @author: jing
 * @create: 2025-07-22 17:26
 **/

public class _03HashMapChain {
    public static void main(String[] args) {
        HashMapChain hashMapChain = new HashMapChain();
        hashMapChain.add(1,"jing");
        hashMapChain.add(2,"wang");
        hashMapChain.add(3,"wang");
        hashMapChain.add(4,"wang");
        hashMapChain.add(5,"wang");
        hashMapChain.add(6,"wang");
        hashMapChain.add(7,"wang");
        hashMapChain.add(8,"wang");
    }
}

class HashMapChain{
    int size; // 键值对数量
    int capacity; // 哈希表容量
    double loadThres; // 触发扩容的负载因子阈值
    int extendRatio; // 扩容倍数
    List<List<Pair>> buckets;

    //构造方法
    public HashMapChain(){
        size = 0;
        capacity = 4;
        loadThres = 0.75;
        extendRatio = 2;
        buckets = new ArrayList<>(capacity);
        for(int i = 0;i<capacity;i++){
            buckets.add(new ArrayList<>());
        }
    }

    //哈希函数
    public int hashFun(int key){
        return key % capacity;
    }

    //负载因子
    public double loadFactor(){
        return size/capacity;
    }

    //查询操作
    public String get(int key){
        int index = hashFun(key);
        List<Pair> bucket = buckets.get(index);
        for(Pair pair : bucket){
            if(pair.key == key){
                return pair.value;
            }
        }
        return null;
    }

    //添加操作
    public void add(int key,String value){
        if(loadFactor() > loadThres){
            extend();
        }
        int index = hashFun(key);
        List<Pair> bucket = buckets.get(index);
        for(Pair pair:bucket){
            if(pair.key == key){
                pair.value = value;
                return;
            }
        }
        Pair pair = new Pair(key, value);
        bucket.add(pair);
        size++;
    }

    //删除操作
    public void delete(int key){
        int index = hashFun(key);
        List<Pair> bucket = buckets.get(index);
        for (Pair pair : bucket) {
            if(pair.key == key){
                bucket.remove(pair);
                size--;
                break;
            }
        }
    }
    //扩容哈希表
    public void extend(){
        System.out.println("开始扩容");
        capacity *= extendRatio;
        List<List<Pair>> bucketsTemp = buckets;
        buckets = new ArrayList<>(capacity);
        for(int i = 0;i<capacity;i++){
            buckets.add(new ArrayList<>());
        }
        size = 0;
        for(List<Pair> bucket : bucketsTemp){
            for(Pair pair:bucket){
                add(pair.key, pair.value);
            }
        }
    }
    //打印哈希表
}
